#include "hash.h"

using std::ios;
using std::cout;
using std::endl;
using std::string;
using std::fstream;

//构造函数
hash::hash()
{
	init();
	record temp;
	int status;
	int t = 0;
	fstream fp("data.txt", ios::in);
	while(fp >> temp.id >> temp.name >> temp.address)				//从文件中读取记录并插入哈希表
	{
		t++;
		status = this->insert(temp);
		if(status == -1)											//有重复记录
			cout << "Duplicate." << endl;
	}
	cout << "Success in inserting " << t << " records." << endl;
}

//初始化函数
void hash::init()
{
	this->count = 0;
	this->size_index = 0;
	this->list_size = hashsize[0];
	int size = this->list_size;
	this->elem = new record[size];
	for (int i = 0; i < size; ++i)
		this->elem[i].id = "";
}

//哈希函数
int hash::get_hash(string id)
{
	int result = 1;
	for(unsigned int i = 0; i < id.size(); i++)
	{
		result ^= id[i];
		result %= this->list_size;
	}
	return result;
}

//查找函数
int hash::search(string id, int &p, int &count)
{
	p = get_hash(id);
	while(this->elem[p].id != "" && this->elem[p].id != id)			//开放定址法处理冲突
	{
		p++;
		count++;
		if(p >= this->list_size)
			p = 0;
	}

	if(this->elem[p].id == id)										//找到记录
		return 1;
	return 0;														//未找到
}

//插入函数
int hash::insert(record e)
{
	int count, p;
	count = 0;
	if(this->search(e.id, p, count) == 1)							//查找所插入的记录是否存在
		return -1;
	else if(count < this->list_size/2)
	{
		this->elem[p] = e;
		this->count++;
		return 0;
	}
	else															//若查找数大于表长的一半，则重建表
	{
		this->recreate();
		this->insert(e);
		return 0;
	}
	return 1;
}

//哈希表重建函数
void hash::recreate()
{
	int i, count = this->count;
	record *p, *elem = new record[count];
	p = elem;

	cout << "Recreated hash" << endl;
	for (i = 0; i < this->list_size; ++i)											//将存在的记录导出
		if (this->elem[i].id != "")
			*p++ = *(this->elem+i);

	this->count = 0;
	this->size_index++;
	this->list_size = hashsize[this->size_index];

	p = new record[this->list_size];
	delete[] this->elem;
	this->elem = p;
	for (i = 0; i < this->list_size; ++i)
		this->elem[i].id = "";
	for (p = elem; p < elem + count; ++p)
		this->insert(*p);											//将记录重新插入重建后的哈希表中
	return;
}
